#ifndef BSTWINDOW_H
#define BSTWINDOW_H

#include <QMainWindow>
#include <QVBoxLayout>
#include <QHBoxLayout>
#include <QTextEdit>
#include <QLineEdit>
#include <QPushButton>
#include <QLabel>
#include <QGroupBox>
#include <QMessageBox>
#include <QComboBox>
#include <QWidget>
#include <QPainter>
#include <QScrollArea>
#include <QDialog>
#include <QDialogButtonBox>
#include <QGridLayout>
#include <QTimer>
#include <QDateTime>

// 可视化状态枚举
enum class VisualizationState {
    None,
    Insert,
    Delete,
    Search
};

// 删除操作子状态
enum class DeleteSubState {
    None,
    FindNode,           // 查找要删除的节点
    FindMaxInLeft,      // 在左子树中找最大节点
    UpdatePointers,     // 更新指针
    ReplaceNode,        // 替换节点
    DeleteOriginal,     // 删除原节点（新增步骤）
    Complete            // 完成
};

struct BSTNode {
    int data;
    BSTNode* left;
    BSTNode* right;
    BSTNode* parent; // 添加父指针用于可视化
    BSTNode(int val, BSTNode* p = nullptr) : data(val), left(nullptr), right(nullptr), parent(p) {}
};

// 简单的随机数生成器
class SimpleRandom {
private:
    long long seed;

public:
    SimpleRandom(long long initialSeed = 1) : seed(initialSeed) {}

    int nextInt(int maxValue) {
        seed = (seed * 1103515245 + 12345) & 0x7FFFFFFF;
        return seed % maxValue;
    }

    // 添加范围参数的重载函数
    int nextInt(int minValue, int maxValue) {
        return minValue + nextInt(maxValue - minValue + 1);
    }
};

// 简单的动态数组实现 - 用于存储整数
class IntVector {
private:
    int* data;
    int capacity;
    int count;

    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        for (int i = 0; i < count; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

public:
    IntVector() : data(new int[10]), capacity(10), count(0) {}

    ~IntVector() {
        delete[] data;
    }

    void push_back(int value) {
        if (count >= capacity) {
            resize(capacity * 2);
        }
        data[count++] = value;
    }

    int operator[](int index) const {
        return data[index];
    }

    int size() const {
        return count;
    }

    void clear() {
        count = 0;
    }

    bool empty() const {
        return count == 0;
    }
};

// 简单的动态数组实现 - 用于存储 BSTNode 指针
class NodeVector {
private:
    BSTNode** data;
    int capacity;
    int count;

    void resize(int newCapacity) {
        BSTNode** newData = new BSTNode*[newCapacity];
        for (int i = 0; i < count; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

public:
    NodeVector() : data(new BSTNode*[10]), capacity(10), count(0) {}

    ~NodeVector() {
        delete[] data;
    }

    void push_back(BSTNode* value) {
        if (count >= capacity) {
            resize(capacity * 2);
        }
        data[count++] = value;
    }

    BSTNode* operator[](int index) const {
        return data[index];
    }

    int size() const {
        return count;
    }

    void clear() {
        count = 0;
    }

    bool empty() const {
        return count == 0;
    }
};

// 简单的哈希表实现用于节点位置存储
class SimpleNodeMap {
private:
    struct NodeEntry {
        BSTNode* key;
        QPoint value;
        NodeEntry* next;

        NodeEntry(BSTNode* k, const QPoint& v) : key(k), value(v), next(nullptr) {}
    };

    static const int TABLE_SIZE = 64;
    NodeEntry** table;
    int entryCount;

    int hash(BSTNode* key) const {
        return (reinterpret_cast<long long>(key) % TABLE_SIZE);
    }

public:
    SimpleNodeMap() : entryCount(0) {
        table = new NodeEntry*[TABLE_SIZE]();
    }

    ~SimpleNodeMap() {
        clear();
        delete[] table;
    }

    void insert(BSTNode* key, const QPoint& value) {
        int index = hash(key);
        NodeEntry* entry = table[index];

        // 检查是否已存在
        while (entry) {
            if (entry->key == key) {
                entry->value = value;
                return;
            }
            entry = entry->next;
        }

        // 创建新条目
        NodeEntry* newEntry = new NodeEntry(key, value);
        newEntry->next = table[index];
        table[index] = newEntry;
        entryCount++;
    }

    bool find(BSTNode* key, QPoint& result) const {
        int index = hash(key);
        NodeEntry* entry = table[index];

        while (entry) {
            if (entry->key == key) {
                result = entry->value;
                return true;
            }
            entry = entry->next;
        }
        return false;
    }

    void clear() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            NodeEntry* entry = table[i];
            while (entry) {
                NodeEntry* next = entry->next;
                delete entry;
                entry = next;
            }
            table[i] = nullptr;
        }
        entryCount = 0;
    }

    int size() const {
        return entryCount;
    }
};

class BSTVisualizationWidget : public QWidget
{
    Q_OBJECT

public:
    explicit BSTVisualizationWidget(QWidget *parent = nullptr)
        : QWidget(parent), root(nullptr), currentVisited(nullptr), targetNode(nullptr),
        newNode(nullptr), replacementNode(nullptr), visualizationState(VisualizationState::None),
        deleteSubState(DeleteSubState::None), m_newNodeParent(nullptr), m_newNodeIsLeftChild(false),
        m_deleteTarget(nullptr), m_maxInLeft(nullptr), m_maxInLeftParent(nullptr),
        m_nodeToDelete(nullptr) {}

    void setRoot(BSTNode* rootNode) {
        root = rootNode;
        currentVisited = nullptr;
        targetNode = nullptr;
        newNode = nullptr;
        replacementNode = nullptr;
        visualizationState = VisualizationState::None;
        deleteSubState = DeleteSubState::None;
        m_newNodeParent = nullptr;
        m_newNodeIsLeftChild = false;
        m_deleteTarget = nullptr;
        m_maxInLeft = nullptr;
        m_maxInLeftParent = nullptr;
        m_nodeToDelete = nullptr;
        update();
    }

    void setVisualizationState(VisualizationState state) {
        visualizationState = state;
        update();
    }

    void setDeleteSubState(DeleteSubState state) {
        deleteSubState = state;
        update();
    }

    void setCurrentVisited(BSTNode* node) {
        currentVisited = node;
        update();
    }

    void setTargetNode(BSTNode* node) {
        targetNode = node;
        update();
    }

    void setNewNode(BSTNode* node) {
        newNode = node;
        update();
    }

    void setReplacementNode(BSTNode* node) {
        replacementNode = node;
        update();
    }

    // 添加设置新节点位置信息的方法
    void setNewNodePositionInfo(BSTNode* parent, bool isLeftChild) {
        m_newNodeParent = parent;
        m_newNodeIsLeftChild = isLeftChild;
        update();
    }

    // 设置删除操作中的关键节点
    void setDeleteNodes(BSTNode* deleteTarget, BSTNode* maxInLeft, BSTNode* maxInLeftParent) {
        m_deleteTarget = deleteTarget;
        m_maxInLeft = maxInLeft;
        m_maxInLeftParent = maxInLeftParent;
        update();
    }

    // 设置要删除的节点
    void setNodeToDelete(BSTNode* node) {
        m_nodeToDelete = node;
        update();
    }

    void resetVisualization() {
        currentVisited = nullptr;
        targetNode = nullptr;
        newNode = nullptr;
        replacementNode = nullptr;
        visualizationState = VisualizationState::None;
        deleteSubState = DeleteSubState::None;
        m_newNodeParent = nullptr;
        m_newNodeIsLeftChild = false;
        m_deleteTarget = nullptr;
        m_maxInLeft = nullptr;
        m_maxInLeftParent = nullptr;
        m_nodeToDelete = nullptr;
        update();
    }

    QSize sizeHint() const override {
        return QSize(1200, 800); // 推荐大小
    }

signals:
    void visualizationStepCompleted();

protected:
    void paintEvent(QPaintEvent* event) override;

private:
    void drawTree(QPainter& painter, BSTNode* node, int x, int y, int level, int maxLevel);
    int getTreeHeight(BSTNode* node) const;
    int max(int a, int b) const { return a > b ? a : b; }

    BSTNode* root;
    BSTNode* currentVisited;  // 当前正在访问的节点
    BSTNode* targetNode;      // 查找的目标节点
    BSTNode* newNode;         // 新插入的节点
    BSTNode* replacementNode; // 替换节点
    VisualizationState visualizationState;
    DeleteSubState deleteSubState;

    // 新节点位置信息
    BSTNode* m_newNodeParent;
    bool m_newNodeIsLeftChild;
    QPoint m_newNodePosition;

    // 删除操作中的关键节点
    BSTNode* m_deleteTarget;
    BSTNode* m_maxInLeft;
    BSTNode* m_maxInLeftParent;

    // 要删除的节点
    BSTNode* m_nodeToDelete;
};

class BSTWindow : public QMainWindow
{
    Q_OBJECT

public:
    BSTWindow(QWidget *parent = nullptr);
    ~BSTWindow();

signals:
    void returnToMainMenu();

private slots:
    void onInputData();
    void onInsert();
    void onDelete();
    void onSearch();
    void onClear();
    void onGenerateRandom();
    void onReturnToMainMenu();
    void onVisualizationStep();
    void onVisualizationFinished();

private:
    void setupUI();
    void updateDisplay();
    void clearTree(BSTNode* node);
    BSTNode* insertNode(BSTNode* node, int value, BSTNode* parent = nullptr);
    BSTNode* deleteNode(BSTNode* node, int value);
    BSTNode* findMin(BSTNode* node);
    BSTNode* findMax(BSTNode* node);
    bool searchNode(BSTNode* node, int value);
    void inorderTraversal(BSTNode* node, QString& result);
    BSTNode* buildBSTFromValues(const IntVector& values);
    int getTreeHeight(BSTNode* node);
    int max(int a, int b) const { return a > b ? a : b; }

    // 随机数生成函数 - 参考二叉树代码
    int randomInt(int min, int max);

    // 可视化操作函数
    void startInsertVisualization(int value);
    void startDeleteVisualization(int value);
    void startSearchVisualization(int value);

    // 可视化步骤处理函数
    void handleStandardVisualizationStep();
    void handleDeleteVisualizationStep();
    void handleInsertVisualizationStep();
    void handleSearchVisualizationStep();

    // 对话框输入函数
    QString getInputDialog(const QString& title, const QString& label, const QString& placeholder = "");
    int getIntegerInputDialog(const QString& title, const QString& label, bool* ok = nullptr);

    BSTNode* m_root;
    int m_size;

    QTextEdit *m_display;

    BSTVisualizationWidget *m_visualizationWidget;
    QScrollArea *m_scrollArea;
    QTimer *m_animationTimer;

    // 可视化状态变量
    NodeVector m_operationPath;
    int m_currentStepIndex;
    VisualizationState m_currentVisualization;
    DeleteSubState m_currentDeleteSubState;
    int m_operationValue;
    BSTNode* m_foundNode;
    BSTNode* m_newNode;
    BSTNode* m_replacementNode;
    BSTNode* m_maxInLeft;
    bool m_operationSuccess;

    // 删除操作中的关键节点指针
    BSTNode* m_deleteTargetParent;
    BSTNode* m_deleteTargetLeft;
    BSTNode* m_deleteTargetRight;
    BSTNode* m_maxInLeftParent;
    bool m_maxInLeftIsRightChild;

    // 要删除的节点
    BSTNode* m_nodeToDelete;

    // 随机数生成器
    SimpleRandom m_random;
};

#endif // BSTWINDOW_H
